#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define INVALID -1
#define TOTAL_S 12
#define TOTAL_E 30
#define P_SIZE 3
#define PF_SIZE 3
//指令数据
struct exec_type
{
	int sn;           /*指令序列号*/
	int pn;           /*指令所在页号*/
}exec[TOTAL_E];
//页表数据
struct pt_type
{
	int pn;           /*页号*/
	int pfn;          /*页面所在内存区的页帧pageframe号(块号)*/
	int age;         /*在内存中的驻留时间*/
}pt[TOTAL_S/P_SIZE];    /*页面结构数组*/
//物理快数据
struct pf_type          /*页面控制结构，模拟内存缓冲区中的链式结构*/
{
	int pfn;            /*内存区页帧号*/
	int pn;
	struct pf_type *next;
};
//记录指令位置链表
struct list{
	int position[TOTAL_E];//最多指令位置
	int pt;//当前位置
}spList[TOTAL_S/P_SIZE];//每条指令坐在页的位置列表
/* freepf_head为内存区页面控制结构的空闲页帧头指针，*busypf_head为忙页帧头指针，*busypf_tail忙页帧尾指针*/
struct pf_type *pf_head=NULL,*freepf_head=NULL,*busypf_head=NULL,*busypf_tail=NULL;
void initialize_e();
void initialize_pt();
void initialize_pf();
void initialize_plist();
void FIFO();
void LRU();
void CLOCK();
void OPT();
void ptMenu();
int main()
{
	ptMenu();
}
//初始化指令
void initialize_e()
{
	int m1,m2,m3,i;
	srand(time(NULL));
	for(i=0;i<TOTAL_E;i+=6)              
	{
		m1=(int)(rand()*1.0/RAND_MAX*(TOTAL_S-1));
		exec[i].sn=m1;
		exec[i+1].sn=m1+1;
		m2=(int)(rand()*1.0/RAND_MAX*m1);
		exec[i+2].sn=m2;
		exec[i+3].sn=m2+1;
		m3=(int)(rand()*1.0/RAND_MAX*(TOTAL_S-m2-3)+(m2+2));
		exec[i+4].sn=m3;
		exec[i+5].sn=m3+1;
	}
	//printf("The num of instructiong is:%d\n",TOTAL_S);
	printf("指令条数有:%d\n",TOTAL_S);
	printf("指令数量有:%d\n",TOTAL_E);
	printf("指令序列如下:\n");
	for (i=0;i<TOTAL_E;i++)
	{
		printf("%4d",exec[i].sn);     /* 按指令执行的顺序输出指令序号0-11*/
		if((i+1)%10==0)
			printf("\n");
	}

	printf("\n页的大小为:%d\n",P_SIZE);
	printf("页表数目为:%d\n",TOTAL_S/P_SIZE);
	printf("指令对应页号如下:\n");
	for (i=0;i<TOTAL_E;i++)
	{
		exec[i].pn=exec[i].sn/P_SIZE;       /* 初始化指令所在页号，并输出页号*/
		printf("%2d :page[ %2d ]",exec[i].sn,exec[i].pn);
		if((i+1)%6==0)
			printf("\n");
	}
}
//初始化位置列表
void initialize_plist(){
	//初始化页位置指针
	for(int i=0;i<TOTAL_S/P_SIZE;i++){
		spList[i].pt=0;
	}
	//设置每个指令所在页的位置
	for (int i=0;i<TOTAL_E;i++)
	{
		int pt=spList[exec[i].pn].pt;
		spList[exec[i].pn].position[pt]=i;
		spList[exec[i].pn].pt++;
	}
	//将位置指针归零
	for (int i=0;i<TOTAL_S/P_SIZE;i++)
	{
		spList[i].pt=0;
	}
	//查看页位置信息 
//	for(int i=0;i<TOTAL_S/P_SIZE;i++){
//		printf("%3d  ",i);
//		for(int j=0;j<TOTAL_E;j++){
//			printf("%3d ",spList[i].position[j]);
//		}
//		printf("\n");
//	}
}
//初始化页表
void initialize_pt()               /*初始化页面结构数组，置页号，页帧-1，表明页不在内存*/
{
	int i;
	for (i=0;i<TOTAL_S/P_SIZE;i++)
	{
		pt[i].pn=i;
		pt[i].pfn=INVALID;
		pt[i].age=INVALID;
		printf("\t页号%d,块号\t%d\n",pt[i].pn,pt[i].pfn);
	}
}
//初始化物理快
void initialize_pf()                  /*初始化页面控制结构*/
{
	pf_head=NULL;
	int i;
	struct pf_type *p;
	for(i=0;i<PF_SIZE;i++)
	{
		p=(struct pf_type*)malloc(sizeof(struct pf_type));
		p->pfn=i;
		p->pn=INVALID;
		p->next=pf_head;
		pf_head=p;
	}
	freepf_head=pf_head;      /*空页帧队列头指针指向pf[0]*/
	busypf_head=busypf_tail=NULL;         /*忙页帧队列头尾链接*/
}

void OPT(){
	int diseffect=0;
	struct pf_type *p, *tmp, *ftmp,*fftmp;
	initialize_pt();
	initialize_pf();
	initialize_plist();
	for(int i=0;i<TOTAL_E;i++)
	{
		//不再块中
		if(pt[exec[i].pn].pfn==INVALID){
			diseffect++;
			//块满
			if(freepf_head==NULL){
				p=busypf_head;
				tmp=p;
				ftmp=p;
				fftmp=p;
				//最久的指针，位置，页号
				int max_pt=0, max_pst=0;
				//按照位置先后,置换
				while(p!=NULL){
					int spt=spList[p->pn].pt;//当前物理快指令所在页的指针
					
					//如果该指令以后一直不用，即position[pt]==0,就换出,而后放入对尾
					if(spList[p->pn].position[spt]==0){
						tmp=p;
						break;
					}else{
					//找到最久不用的指令
						//是头链就保存副本
						if(p==freepf_head){
							max_pt=spList[p->pn].pt;
							max_pst=spList[p->pn].position[max_pt];
						}else{
							//当前物理链的位置比较大
							if(spList[p->pn].position[spt]>max_pst){
								fftmp=ftmp;//记录当前的
								tmp=p;
								max_pt=spList[p->pn].pt;
								max_pst=spList[p->pn].position[max_pt];
							}
						}
					}
					ftmp=p;
					p=p->next;
				}
				//置换
				pt[tmp->pn].pfn=INVALID;
				tmp->pn=exec[i].pn;
				pt[exec[i].pn].pfn=tmp->pfn;
				//是头链
				if(tmp==busypf_head){
					//插入尾部
					busypf_head=busypf_head->next;
					tmp->next=NULL;
					busypf_tail->next=tmp;
					busypf_tail=tmp;
				}else{
					if(tmp->next!=NULL){
						fftmp->next=tmp->next;
						tmp->next=NULL;
						busypf_tail->next=tmp;
					}
					busypf_tail=tmp;
				}
				//更新所在页
				spList[tmp->pn].pt++;
			}else{
			//块不满
				//尾插
				p=freepf_head;
				freepf_head=freepf_head->next;
				p->next=NULL;
				p->pn=exec[i].pn;
				pt[exec[i].pn].pfn=p->pfn;         /*按FIFO方式调新页面入内存*/
				if(busypf_tail==NULL)
					busypf_head=busypf_tail=p;
				else
				{
					busypf_tail->next=p;
					busypf_tail=p;              /*将新调入的页插入忙页帧队列的队尾*/
				}
				//插入后刷新位置列表
				spList[exec[i].pn].pt++;
			}
		}else{
		//在块中，刷新位置列表
			spList[exec[i].pn].pt++;
		}
		//查看
		printf("%3d 指令:%3d\t所在页号:%3d\t物理块:",i, exec[i].sn, exec[i].pn);
		p=busypf_head;
		while(p!=NULL){
			printf("%3d ",p->pn);
			p=p->next;
		}
		printf("\n");
		
	}
	printf("OPT:\tdiseffect:%d\tTOTAL_E:%d\tPage break(缺页率):%.2f%%\n",diseffect,TOTAL_E,diseffect*100.0/TOTAL_E);
}

void FIFO()
{
	int i,j,diseffect=0;
	struct pf_type *p;
	initialize_pt();
	initialize_pf();
	for(i=0;i<TOTAL_E;i++)
	{
		if(pt[exec[i].pn].pfn==INVALID)              /*页面失效*/
		{
			diseffect++;
			if(freepf_head==NULL)               /*无空闲页面*/
			{
				p=busypf_head;
				busypf_head=busypf_head->next;
				p->next=NULL;
				freepf_head=p;                     /*释放忙页帧队列的第一个页面*/
				pt[p->pn].pfn=INVALID;            /*修改换出的页所对应的页表项中的页帧号*/
			}
			p=freepf_head;
			freepf_head=freepf_head->next;
			p->next=NULL;
			p->pn=exec[i].pn;
			pt[exec[i].pn].pfn=p->pfn;         /*按FIFO方式调新页面入内存*/
			if(busypf_tail==NULL)
				busypf_head=busypf_tail=p;
		 	else
			{
				busypf_tail->next=p;
 				busypf_tail=p;              /*将新调入的页插入忙页帧队列的队尾*/
			}
	   	}

		//查看
		printf("%3d 指令:%3d\t所在页号:%3d\t物理块:",i, exec[i].sn, exec[i].pn);
		p=busypf_head;
		while(p!=NULL){
			printf("%3d ",p->pn);
			p=p->next;
		}
		printf("\n");
	}
	printf("FIFO:\tdiseffect:%d\tTOTAL_E:%d\tPage break(缺页率):%.2f%%\n",diseffect,TOTAL_E,diseffect*100.0/TOTAL_E);
}


void LRU()
{
	int diseffect=0;
	struct pf_type* p,* tmp;//tmp记录p上一个链表
	initialize_pt();
	initialize_pf();	
	//遍历执行序列
	for(int i=0;i<TOTAL_E;i++){
		/*查看指令所在页表是否在块中*/
		//不在块中
		if(pt[exec[i].pn].pfn==INVALID){
			diseffect++;
			/*判断块满*/
			if(freepf_head==NULL){
				//块满，置换头部最不常用的
				//更新块信息
				pt[busypf_head->pn].pfn=INVALID;//将原来的置为-1，未分配
				pt[exec[i].pn].pfn=busypf_head->pfn;
				busypf_head->pn=exec[i].pn;
				//放入尾部
				tmp=busypf_head;
				busypf_head=tmp->next;
				tmp->next=NULL;
				busypf_tail->next=tmp;
				busypf_tail=tmp;
			}else{
				//块没满
				//放入尾部最常用
				tmp=freepf_head;
				tmp->pn=exec[i].pn;
				pt[exec[i].pn].pfn=tmp->pfn;
				freepf_head=freepf_head->next;
				tmp->next=NULL;
				//如果块中无页
				if(busypf_tail==NULL){
					busypf_head=busypf_tail=tmp;
				}else{
					busypf_tail->next=tmp;
					busypf_tail=busypf_tail->next;
				}
			}
		}else{
		//在块中
			//找到在busy中的连表进行操作
			p=busypf_head;
			while(p!=NULL){
				if(p->pfn==pt[exec[i].pn].pfn && p->pn==exec[i].pn){//找到物理快
					//如果不是尾
					if(p!=busypf_tail){
						if(p==busypf_head){//是头链就将头链给下面一个元素
							busypf_head=busypf_head->next;
						}else{//不是头，将其放入尾部，连头链条
							tmp->next=p->next;
						}
						p->next=NULL;
						busypf_tail->next=p;
						busypf_tail=p;
					}
					//是尾不用动
				}
				tmp=p;
				p=p->next;
			}
		}
		//查看
		printf("%3d 指令:%3d\t所在页号:%3d\t物理块:",i, exec[i].sn, exec[i].pn);
		p=busypf_head;
		while(p!=NULL){
			printf("%3d ",p->pn);
			p=p->next;
		}
		printf("\n");
	}
	printf("LRU:\tdiseffect:%d\tTOTAL_E:%d\tPage break(缺页率):%.2f%%\n",diseffect,TOTAL_E,diseffect*100.0/TOTAL_E);
}

void ptMenu()
{
	initialize_e();
	int index=0;
	do
	{
		printf("\n选择对应的分配算法\n");
		printf("1.FIFO\t2.LRU\t3.OPT\t4.退出\n");
		scanf("%d",&index);
		switch(index)
		{
			case 1:
				printf("FIFO分配算法:\n");
				FIFO();
				break;
			case 2:
				printf("LRU分配算法:\n");
				LRU();
				break;
			case 3:
				printf("OPT分配算法:\n");
				OPT();
				break;
			default:break;
		}
	}while(index!=4);
}